package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 * <p>
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
 * 内存消耗：35.3 MB, 在所有 Java 提交中击败了77.62%的用户
 **/
public class No013 {
    /**
     * 行
     */
    private int m;
    /**
     * 列
     */
    private int n;
    /**
     * 相加的边界值
     */
    private int k;
    /**
     * 访问痕迹
     */
    private boolean[][] visited;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0);
    }

    private int dfs(int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || (x / 10 + x % 10 + y / 10 + y % 10) > k || visited[x][y]) {
            return 0;
        }

        visited[x][y] = true;
        return 1 + dfs(x + 1, y) + dfs(x, y + 1);
    }

//    执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
//    内存消耗：35.3 MB, 在所有 Java 提交中击败了68.58%的用户
//    private int[][] direct = {{1, 0}, {0, 1}};
//    private boolean[][] visited;
//    private int count = 0;
//    private int row;
//    private int col;
//
//    public int movingCount(int m, int n, int k) {
//        this.visited = new boolean[m][n];
//        this.row = m;
//        this.col = n;
//        dfs(0, 0, k);
//        return count;
//    }
//
//    private void dfs(int x, int y, int k) {
//        if (!isInBounds(x, y) || visited[x][y]) {
//            return;
//        }
//
//        if (x / 10 + x % 10 + y / 10 + y % 10 <= k) {
//            count++;
//            visited[x][y] = true;
//            for (int i = 0; i < 2; i++) {
//                dfs(x + direct[i][0], y + direct[i][1], k);
//            }
//        }
//    }
//
//    private boolean isInBounds(int x, int y) {
//        return x >= 0 && x < row && y >= 0 && y < col;
//    }
}
